keywords: Cryptography, Privacy preserving computation, Secure function evaluation, Oblivious transfer

ABSTRACT

contributions: computationally secure protocols of

• 1-out-of-N OT: only log N executions of a 1-out-of-2 OT protocol

• k-out-of-N OT: more eff. than k repetitions of 1-out-of-N OT

• oblivious transfer with adaptive queries.

1 Introduction

1.1 Oblivious Transfer

Oblivious Transfer (OT)

Note that this transformation takes DH-tuples to DH-tuples, and non-DH-tuples to non-DH-tuples. Furthermore, the new exponents are independent of the originals. This is easy to see if we start with a DH tuple.

https://crypto.stanford.edu/pbc/notes/crypto/ot.html

1.2 Correctness and Security Definitions

• The Receiver's Security:

receiver: 计算上不可区分获得的值和随机值

• The Sender's Security:

sender: 对于sender，要求real implementation of the protocol 和 ideal model不可区分，即不可以获得比ideal model 下更多的信息 ideal implementation: a trusted party

formal def:

2 Protocols for 1-out-of-N Oblivious Transfer

• assumption: block ciphers or keyed one-way hash functions can be modeled as PRF.

PRF $F_K(x)$:

• block cipher with key K and encrypting x

• keying a hash function with K and applying it to x

• main idea of 1-out-of-N: use a small set of keys(logN) and mask each input with a combination of a different subset of the keys 用logN个不同的keys，通过不同的密钥组合来加密不同的输入

• p.s.: the keys are not applied directly(insecure) input $X_I$: the value $F_K(I)$ is used for masking 不能直接把密钥应用到明文上加密（比如异或的形式）

有两种实现1-out-of-N OT的协议： 一种是使用logN次 1-out-of-2 OT协议 另一种是使用递归式的方法：将1-out-of-N分为两个1-out-of-$\sqrt{N}$ OT

两个协议中最主要的是transfer stage中调用1-out-of-2。 不过后一种协议再初始化阶段是O(N)的复杂度，另一个是O(NlogN)的复杂度。

2.1 A Protocol for 1-out-of-N OT

Protocol

• sender B input $X_1,X_2,...,X_N$, receiver want's to learn $X_I$

1. sender B prepares $l$ random pairs of keys B准备logN个密钥对，每个密钥对中一个对应比特0，一个对应比特1。对每一个$X_I$都做mask操作，具体来说就是根据$I$的比特位来选择密钥，用PRF的output依次mask。

2. A and B engage in a 1-out-of-2 OT on $<K_j^0,K_j^1>$ A和B执行logN次 1-out-of-2 OT，得到A的选择$I$对应比特位的密钥。

3. B sends to A the string Y B向A发送N个加密后的Y = E(X)。

4. A reconstructs X A只有他所选择值的密钥，只能解密出其中一个。

Complexity

• preprocessing(step 1): $N\log{N}$ evaluations of the pseudo-random function FK 每一个X都要logN个密钥对其mask。

• transfer stage: $\log{N}$ invocations of the 1-out-of-2 OT protocol

invocation: a request for help

Improvement

2.2 A Recursive Protocol for 1-out-of-N OT

protocol

• sender B input $X_1,X_2,...,X_N$, receiver want's to learn $X_I$

1. B prepares two sets of $\sqrt{N}$ randomly chosen keys. B arranges the N inputs in a $\sqrt{N}\times\sqrt{N}$ matrix. B准备两组sqrt(N)的随机密钥。再把这N个值组合为一个矩阵，这样就可以用行列来索引。B对每个值都用行列索引来加密。

2. A and B engage in a 1-out-of-$\sqrt{N}$ OT protocol A 和B执行1-out-of-$\sqrt{N}$ OT，让A得到目标选择的行列密钥。

3. B sends to A all the Y

4. A reconstructs X A只有目标选择对行列密钥，所以只能得到一个值。

complexity

• total = 2N evaluations of FK for preprocessing + 2 invocations of the 1-out-of-sqrt(N) protocol for transfer

• 2 1-out-of-sqrt(N) OT
  • preprocess: $2\sqrt{N} \log \sqrt{N} = \sqrt{N}\log N$evaluations for FK
  • transfer stage: $2\log\sqrt{N} = \log N$ 1-out-of-2 OT 所以说两个协议调用1-out-of 2的次数是一样的

• totol invocations of PRF: $\sqrt{N}\log N + 2N$

• total calls of 1-out-of-2 OT: $\log N$

2.1协议被认为是 logn维密钥加密的，而2.2协议被认为是2维加密